
lst = [90, 89, 17, 99, 78, 6, 55, 98]

# 归并排序
def sort_lst(lst):
    if len(lst) == 1:
        return lst
    else:
        lst_1 = lst[:len(lst)//2]
        lst_2 = lst[len(lst)//2:]
        a = sort_lst(lst_1)
        b = sort_lst(lst_2)
        return merge(a, b)

def merge(a,b):
    lst=[]
    while a and b:
        if a[0] < b[0]:
            lst.append(a.pop(0))
        else:
            lst.append(b.pop(0))

    return lst+a+b
print(sort_lst(lst))


